package leetcode_121_140;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class longestConsecutive_128 {
    /**
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     */
    public int longestConsecutive(int[] nums) {
        /**
         * 题意大概是
         * 100,4,200,1,3,2      ->    1 2 3 4
         * 思路是顺序遍历每一个数字，记录每个数字所在的连续的数字序列的期望数字，即可以与其连接的数字
         * 维护一个实时最大长度
         * 这个想法实现起来太繁琐了
         * 放弃
         */
        int maxLen=1;
        //方便查询对应期望数字对应的数字序列 使用hashmap
        HashMap<Integer,Object[]>map=new HashMap<>();
        //key, 一个数字序列所期待的数字，value，数组:[序列另一端的期待数字，数字所在序列的实时长度，是否是该序列的前端期望值 ]
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])) { //如果当前数字是某个序列的期待数字
                //如果当前序列的期望数字也是别的序列的期望数字，将长度连接
                if(map.containsKey(nums[i]+1)) {

                }
                int other= (int) map.get(nums[i])[0];  //另一端的期望值
                int newLen=(int) map.get(nums[i])[1]+1; //序列长度+1
                boolean isFront= (boolean) map.get(nums[i])[2];
                int newNum=isFront?nums[i]+1:nums[i]-1;
                Object[] arr={other,newLen,isFront};  //设置新数组
                map.put(newNum,arr);
                map.remove(nums[i]); //完成更新
                arr[0]=newNum;  //更新另一端期望值所对应的数字
                map.put(other,arr);
                maxLen=Math.max(newLen,maxLen);      //更新最大长度
            }else {  //如果当前数字不是已记录的任何序列的期望数字
                //如果当前数字的期望数字也是别人的期望数字，将长度连接
                if(map.containsKey(nums[i]+1)) {  //当前数字的后端期望数字，是别的序列的前端期望数字
                    int newLen=(int) map.get(nums[i]+1)[1]+1; //序列长度+1
                    Object[] arr={null,newLen,null};  //设置新数组
                    map.put(nums[i]+1,arr);//更新
                }else {
                    Object[] arr1={nums[i]+1,1,false};  //设置新数组,大数作为后端
                    map.put(nums[i]-1,arr1);
                }
                if(map.containsKey(nums[i]-1)) {  //当前数字的前端期望数字，是别的序列的后端期望数字
                    int newLen=(int) map.get(nums[i]+1)[1]+1; //序列长度+1
                    Object[] arr={null,newLen,null};  //设置新数组
                    map.put(nums[i]+1,arr);//更新
                }else {
                    Object[] arr2 = {nums[i] - 1, 1, true};  //设置新数组
                    map.put(nums[i] + 1, arr2);
                }
            }
        }
        return maxLen;
    }



    /**
     * 思路是将数字全部存入hash表中，便于判断是否存在某个数字
     * 然后只寻找不存在前一位的数字，这些数字必然是一个序列的开头
     * 然后进行依次查找大一位的数字，只需要查找nums_len次
     */
    public int longestConsecutive2(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        //数字全部存入hash表中
        for (int num : nums) {
            num_set.add(num);
        }

        //最长序列
        int longestStreak = 0;

        for (int num : num_set) {
            //只判断不含有前一位的数字
            if (!num_set.contains(num - 1)) {
                int currentStreak = 1;

                //循环找后一位
                while (num_set.contains(num + 1)) {
                    num++;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }


    /**
     * 尝试偷懒，直接对数组排序处理
     * 甚至更快。。可能是用例比较少，因为排序必然复杂度超了
     */
    public int longestConsecutive3(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        Arrays.sort(nums);
        int maxLength = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                count++;
            } else if (nums[i] == nums[i - 1]) {
                continue;
            } else {
                maxLength = Math.max(maxLength, count);
                count = 1;
            }
        }
        maxLength = Math.max(maxLength, count);
        return maxLength;
    }
}
